/*
 *  insertion sort using the binary search algorithm
 *  Keys:
 *  1. determine lo and hi
 *  2. how to update lo and hi while iterate
 */
package algs4.sort;

public class BinaryInsertion
{
    /* Static Methods */
    public static void sort(Comparable[] a) {
        int n = a.length;

        for (int i = 1; i < n; i++) {
            int        lo = 0;
            int        hi = i;
            Comparable v  = a[i];

            // binary search to determine index to insert v(a[i])
            while (lo < hi) {
                int mid = (lo + hi) / 2;

                if (v.compareTo(a[mid]) < 0) hi = mid;
                else                         lo = mid + 1;
            }

            for (int j = i; j > lo; j--) a[j] = a[j-1];

            a[lo] = v;
        }
    }

    public static void sort(Comparable[] a, int st, int ed) {
        for (int i = st + 1; i <= ed; i++) {
            int        lo = st;
            int        hi = i;
            Comparable v  = a[i];

            // binary search to determine index to insert v(a[i])
            while (lo < hi) {
                int mid = (lo + hi) / 2;

                if (v.compareTo(a[mid]) < 0) hi = mid;
                else                         lo = mid + 1;
            }

            for (int j = i; j > lo; j--) a[j] = a[j-1];

            a[lo] = v;
        }
    }
}
